﻿#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <map>
#include <string>

using namespace std;


//map底层的红⿊树节点中的数据，使⽤pair<Key, T>存储键值对数据。
//typedef pair<const Key, T> value_type;
//int main()
//{
//	// initializer_list构造,这里其实是{"left", "左边"}先隐式类型转换成pair(const T1& a, const T2& b)，再调用map的map (initializer_list<value_type> il)构造
//	map<string, string> dict = { {"left", "左边"}, {"right", "右边"},{"insert", "插入"},{ "string", "字符串" } };
//
//	map<string, string>::iterator it = dict.begin();
//
//	while (it != dict.end())
//	{
//		//cout << (*it).first << ":" << (*it).second << endl;
//
//		// 第⼀个->是迭代器运算符重载，返回pair*，第⼆个箭头是结构指针解引⽤取pair数据
//		//cout << it.operator->()->first << ":" << it.operator->()->second << endl;
//		cout << it->first << ":" << it->second << endl;
//		++it;
//	}
//
//	cout << endl;
//
//	pair<string, string> kv1 = { "first","第一个" };
//	dict.insert(kv1);
//
//	dict.insert(pair<string, string>("second", "第二个"));
//
//	dict.insert(make_pair("sort", "排序"));
//	dict.insert({ "auto","自动的" });//隐式类型转换成pair类型
//
//	// "left"已经存在，插⼊失败
//	// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
//	dict.insert({ "left","左边，剩余" });
//
//	for (auto& e : dict)
//	{
//		cout << e.first << ":" << e.second << endl;
//	}
//
//	//string str;
//
//	//while (cin >> str)
//	//{
//	//	// 查找k，返回k所在的迭代器，没有找到返回end()
//	//	auto ret = dict.find(str);
//
//	//	if (ret != dict.end())
//	//	{
//	//		cout <<"->" << ret->second << endl;
//	//	}
//	//	else
//	//	{
//	//		cout << "not found" << endl;
//	//	}
//	//}
//
//	auto it1 = dict.begin();
//	dict.erase(it1);
//
//	string x;
//	cin >> x;
//
//	int num = dict.erase(x);// 删除x，x不存在返回0，存在返回1
//	if (num == 0)
//	{
//		cout << "不存在" << endl;
//	}
//	
//	for (auto& e : dict)
//	{
//		cout << e.first << ":" << e.second << endl;
//	}
//	cout << endl;
//
//	return 0;
//}

// insert插⼊⼀个pair<key, T>对象
// 1、如果key已经在map中，插⼊失败，则返回⼀个pair<iterator,bool>对象，返回pair对象first是key所在结点的迭代器，second是false
// 2、如果key不在在map中，插⼊成功，则返回⼀个pair<iterator,bool>对象，返回pair对象first是新插⼊key所在结点的迭代器，second是true
// 也就是说⽆论插⼊成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭代器
// 那么也就意味着insert插⼊失败时充当了查找的功能，正是因为这⼀点，insert可以⽤来实现operator[]
// 需要注意的是这⾥有两个pair，不要混淆了，⼀个是map底层红⿊树节点中存的pair<key, T>，另⼀个是insert返回值pair<iterator, bool>

//typedef pair<const Key, T> value_type;
//pair<iterator, bool> insert(const value_type& val);
// 
//mapped_type& operator[] (const key_type& k);
// 
// operator的内部实现
//mapped_type& operator[] (const key_type& k)
//{
//	// 1、如果k不在map中，insert会插⼊k和mapped_type默认值（内置类型，比如int就是0，自定义类型调用默认构造），同时[]返回结点中存储
//	mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊ + 修改功能
// 
//	// 2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的
//	迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找 + 修改的功能
// 
//	pair<iterator, bool> ret = insert({ k, mapped_type() });
//	iterator it = ret.first;//指向pair<iterator, bool>中的iterator，即插入或者查找到的的那个结点
//	return it->second;//返回的是那个结点的value值
//}

//int main()
//{
//	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };
//	map<string, int> countMap;
//
//	/*for (const auto& str : arr)
//	{
//		auto ret = countMap.find(str);
//		if (ret != countMap.end())
//		{
//			ret->second++;
//		}
//		else
//		{
//			countMap.insert({ str, 1 });
//		}
//	}*/
//
//	for (const auto& str : arr)
//	{
//		// []先查找⽔果在不在map中
//        // 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 0}（int默认值为0），同时返回次数的引⽤，++⼀下就变成1次了
//		// 2、在，则返回⽔果对应的次数++
//		countMap[str]++;
//	}
//
//	for (auto& e : countMap)
//	{
//		cout << e.first << ":" << e.second << endl;
//	}
//	cout << endl;
//
//	return 0;
//}

//int main()
//{
//	map<string, string> dict;
//	dict.insert({ "insert","插入" });
//
//	// key不存在->插⼊ {"right", string()}
//	dict["right"];
//
//	//插入+修改
//	dict["sort"] = "排序";
//
//	dict["left"] = "左边";
//	
//	//查找+修改
//	dict["left"] = "左边，其他";
//
//	//存在，查找
//	cout << dict["left"] << endl;
//
//	//不存在，插入
//	cout << dict["apple"] << endl;
//
//	cout << endl;
//
//	for (const auto& e : dict)
//	{
//		cout << e.first << "->" << e.second << endl;
//	}
//
//
//	return 0;
//}

//multimap和map的使⽤基本完全类似，主要区别点在于multimap⽀持关键值key冗余，那么
//insert / find / count / erase都围绕着⽀持关键值key冗余有所差异，这⾥跟set和multiset完全⼀样，⽐如
//find时，有多个key，返回中序第⼀个。其次就是multimap不⽀持[]，因为⽀持key冗余，[]就只能⽀
//持插⼊了，不能⽀持修改。

int main()
{
	multimap<string, string> dict;

	//允许键值冗余
	dict.insert({ "left","左边" });
	dict.insert({ "left","xxx" });
	dict.insert({ "left","yyy" });
	dict.insert({ "left","zzz" });


	for (const auto& e : dict)
	{
		cout << e.first << "->" << e.second << endl;
	}
	

	return 0;
}